#include <vector>
using namespace std;
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //思路：先全部按位异或，找到这两个数的异或结果
        //然后找到最右侧的1，就是这两个唯一出现一次的数的位第一次不同的地方。
        //然后按照这个不同，将所有的数分为两种，分别组内异或就能找出这两个数
        int dif = 0;
        for(auto x : nums){
            dif ^= x;
        }
        int pos = 0;
        for(int i = 0 ; i <= 32 ; i++){
            if((dif>>i) & 1){
                pos = i;
                break;
            } 
        }
        vector<int> v1,v2,ret;
        for(auto x : nums){
            if((x >> pos) & 1){
                v1.push_back(x);
            }else{
                v2.push_back(x);
            }
        }
        int tmp1 =0 ,tmp2 = 0;
        for(auto x : v1 ){
            tmp1 ^= x;
        }
        ret.push_back(tmp1);
        for(auto x : v2){
            tmp2 ^= x;
        }
        ret.push_back(tmp2);
        return ret;
    }
};

int main(){
    vector<int> v {1,2,1,3,2,5};
    Solution().singleNumber(v);
    return 0;
}